package com.wzw.basics.concurrent.cas;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicStampedReference;

/**
 * CAS
 * <p>
 * 全称为Compare-And-Swap，它是一条CPU并发原语。
 * 它的功能是判断内存某个位置的值是否为预期值，如果是则更改为新的值，这个过程是原子的。
 * CAS并发原语体现在JAVA语言中就是sun.misc.Unsafe类中的各个方法。
 * 调用Unsafe类中的CAS方法，JVM会帮我们实现出CAS汇编指令。
 * 这是一种完全依赖于硬件的功能，通过它实现了原子操作。
 * 再次强调，由于CAS是一种系统原语，原语属于操作系统用语范畴，
 * 是由若干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成所谓的数据不一致问题。（原子性）
 * <p>
 * <p>
 * CAS有3个操作数，内存值V，旧的预期值A，要修改的更新值B。
 * 当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。
 * <p>
 * 缺点：
 * 1.循环开销很大，只适用于逻辑操作较为简单的功能
 * 2.只能保证一个共享变量的原子性
 * 3.普通的CAS可能导致ABA问题
 *
 * @author Wangzhiwen
 */
public class CAS {

    public static void main(String[] args) {
        AtomicIncrement.increment();
        AtomicRef.ABA();
    }
}

/**
 * AtomicInteger原子自增原理
 */
class AtomicIncrement {

    /**
     * AtomicInteger原子自增原理
     * Unsafe
     *      是CAS的核心类，由于Java方法无法直接访问底层系统，需要通过本地（native）方法来访问
     *      Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。
     *      Unsafe类存在于sun.misc包中，其内部方法操作可以像C的指针一样直接操作内存，因为Java中CAS操作的执行依赖于Unsafe类的方法。
     *      注意Unsafe类中的所有方法都是native修饰的，也就是说Unsafe类中的方法都直接调用操作系统底层资源执行相应任务
     * 变量valueOffset，表示该变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的。
     * 变量value用volatile修饰，保证了多线程之间的内存可见性。
     */
    public static void increment(){
        AtomicInteger atomicInteger = new AtomicInteger(1);
        /*
         *     public final int getAndIncrement() {
         *         return unsafe.getAndAddInt(this, valueOffset, 1);
         *     }
         *
         *     // var1 代表AtomicInteger对象本身
         *     // var2 代表对象的内存地址偏移量，该对象值的引用地址。
         *     // var4 代表要自增1
         *     public final int getAndAddInt(Object var1, long var2, int var4) {
         *         int var5;
         *         do {
         *             // var5 首先传入当前对象和内存地址值，获取到该int类型变量在主内存中的实际值
         *             var5 = this.getIntVolatile(var1, var2);
         *         // 底层使用UnSafe CAS 比较并交换，传入预期值var5，如果该对象指定的内存中的值与期望值相同，就吧内存中的值加1
         *         // 不断的自旋，直到比较的值与期望值相符才加1并退出循环
         *         } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
         *
         *         return var5;
         *     }
         *
         *
         * 假设线程A和线程B两个线程同时执行getAndAddInt操作（分别跑在不同CPU上) ：
         * 1.AtomicInteger里面的value原始值为3，即主内存中AtomicInteger的value为3，根据JMM模型，线程A和线程B各自持有一份值为3的value的副本分别到各自的工作内存。
         * 2.线程A通过getIntVolatile(var1, var2)拿到value值3，这时线程A被挂起。
         * 3.线程B也通过getIntVolatile(var1, var2)方法获取到value值3，此时刚好线程B没有被挂起并执行compareAndSwapInt方法比较内存值也为3，成功修改内存值为4。
         * 4.线程A恢复，执行compareAndSwapInt方法比较，发现自己手里的值数字3和主内存的值数字4不一致，说明该值己经被其它线程抢先一步修改过了，那A线程本次修改失败，只能重新读取重新来一遍了。
         * 5.线程A重新获取value值，因为变量value被volatile修饰，所以其它线程对它的修改，线程A总是能够看到，线程A继续执行compareAndSwapInt进行比较替换，直到成功。
         */
        atomicInteger.getAndIncrement();
    }

}

/**
 * 原子引用与ABA问题，在CAS比较过程之前就有线程把原来的值改了一次又改回来了。
 *
 * CAS算法实现一个重要前提需要取出内存中某时刻的数据并在当下时刻比较并替换，那么在这个时间差类会导致数据的变化。
 * 比如说一个线程A从内存位置V中取出A，这时候另一个线程B也从内存中取出A，并且线程B进行了一些操作将值变成了B,
 * 然后线程C又将V位置的数据变成A，这时候线程A进行CAS操作发现内存中仍然是A，然后线程A操作成功。
 * 尽管线程A的CAS操作成功，但是不代表这个过程就是没有问题的。
 *
 * 解决办法：使用带时间戳的原子引用类 AtomicStampedReference
 * 原理：
 *      1.提供一个初始的int类型版本号
 *      2.每次执行CAS操作时，除了需要传入期望值与更新值还需要传入当次更新前的版本号和更新完成之后需要变更成为的版本号
 *      3.执行成功CAS操作后，对象的版本号会变更
 */
class AtomicRef {

    public static void ABA(){
        System.out.println("CAS ABA");

        Person old = new Person("old", 100);
        AtomicReference<Person> personAtomicReference = new AtomicReference<>(old);

        // 线程A先通过比较old更新原子引用值为 520
        ThreadDemo threadA = new ThreadDemo("Thread A",personAtomicReference);
        threadA.setOldPerson(old);
        Person temp = new Person("Thread A", 520);
        threadA.setNewPerson(temp);
        threadA.start();

        // 线程B在通过比较引用old更细原子引用为 312 ，但是它执行的比较慢
        ThreadDemo threadB = new ThreadDemo("Thread B", personAtomicReference);
        threadB.setOldPerson(old);
        threadB.setNewPerson(new Person("Thread B",312));
        threadB.start();

        // 线程C再次修改原子引用为old
        ThreadDemo threadC = new ThreadDemo("Thread C", personAtomicReference);
        threadC.setOldPerson(temp);
        threadC.setNewPerson(old);
        threadC.start();
        /* result
         * cas result is true and the new value : Person{name='Thread a temp person', age=520}
         * cas result is true and the new value : Person{name='old', age=100}
         * cas result is true and the new value : Person{name='Thread b update person', age=312}
         */

        System.out.println("CAS ABA use AtomicStampedReference to solve");

        // 初始版本号为 1
        AtomicStampedReference<Person> personAtomicStampedReference = new AtomicStampedReference<Person>(old,1);
        System.out.println("init stamp : " + personAtomicStampedReference.getStamp());

        // 线程D更新引用为temp，更新版本号为 2
        ThreadDemo2 threadD = new ThreadDemo2("Thread D", personAtomicStampedReference);
        threadD.setOldPerson(old);
        threadD.setNewPerson(temp);
        threadD.start();

        // 线程E执行较慢，准备更新引用为 456，版本号更新为 2
        ThreadDemo2 threadE = new ThreadDemo2("Thread E", personAtomicStampedReference);
        threadE.setOldPerson(old);
        threadE.setNewPerson(new Person("Thread E",456));
        threadE.start();

        // 线程F重新更新引用为old，版本号为 3
        ThreadDemo2 threadF = new ThreadDemo2("Thread F", personAtomicStampedReference);
        threadF.setOldPerson(temp);
        threadF.setNewPerson(old);
        threadF.start();
        /*
         * cas result is false and the new value : Person{name='old', age=100} stamp 1
         * cas result is true and the new value : Person{name='Thread A', age=520} stamp 2
         * cas result is false and the new value : Person{name='Thread A', age=520} stamp 2
         */
    }

    static class ThreadDemo extends Thread {

        private Person oldPerson;

        private Person newPerson;

        private final AtomicReference<Person> personAtomicReference;

        public void setOldPerson(Person oldPerson) {
            this.oldPerson = oldPerson;
        }

        public void setNewPerson(Person newPerson) {
            this.newPerson = newPerson;
        }

        @Override
        public void run() {
            // 模拟线程B执行较慢的场景
            if (Thread.currentThread().getName().contains("Thread B")){
                try {
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) {
                    // ignore
                }
            }
            System.out.println("cas result is " + personAtomicReference.compareAndSet(oldPerson, newPerson) + " and the new value : " + personAtomicReference.get());
        }

        public ThreadDemo(String name,AtomicReference<Person> personAtomicReference) {
            super(name);
            this.personAtomicReference = personAtomicReference;
        }
    }

    static class ThreadDemo2 extends Thread {

        private Person oldPerson;

        private Person newPerson;

        private final AtomicStampedReference<Person> personAtomicStampedReference;

        public void setOldPerson(Person oldPerson) {
            this.oldPerson = oldPerson;
        }

        public void setNewPerson(Person newPerson) {
            this.newPerson = newPerson;
        }

        @Override
        public void run() {
            int stamp = personAtomicStampedReference.getStamp();
            // 模拟线程B执行较慢的场景
            if (Thread.currentThread().getName().contains("Thread B") || Thread.currentThread().getName().contains("Thread E")){
                try {
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) {
                    // ignore
                }
            }
            System.out.println("cas result is " + personAtomicStampedReference.compareAndSet(oldPerson, newPerson,stamp,stamp + 1) + " and the new value : " + personAtomicStampedReference.getReference() + " stamp " + personAtomicStampedReference.getStamp());
        }

        public ThreadDemo2(String name,AtomicStampedReference<Person> personAtomicStampedReference) {
            super(name);
            this.personAtomicStampedReference = personAtomicStampedReference;
        }
    }

    static class Person {
        private String name;
        private Integer age;

        public Person(String name, Integer age) {
            this.name = name;
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Integer getAge() {
            return age;
        }

        public void setAge(Integer age) {
            this.age = age;
        }

        @Override
        public String toString() {
            return "Person{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    }
}


